package com.nanbei.huffman;

import cn.hutool.json.JSONUtil;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @ClassDescription:
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/3 16:47
 */
public class HuffmanTree {
    String str;
    HashMap<Character,HuffmanNode> hashMap = new HashMap<>();
    // 用来记录哈夫曼树的根节点
    HuffmanNode root ;

    public HuffmanTree(String str) {
        this.str = str;
        char[] chars = str.toCharArray();

        // 统计字符出现的频率
        for (char aChar : chars) {
            HuffmanNode huffmanNode = hashMap.computeIfAbsent(aChar, HuffmanNode::new);
            huffmanNode.freq++;
        }
        // 构造树
        // 创建优先级队列将所有节点存放进去
        PriorityQueue<HuffmanNode> huffmanQueue = new PriorityQueue<>(
                Comparator.comparingInt(HuffmanNode::getFreq));
        huffmanQueue.addAll(hashMap.values());
        while (huffmanQueue.size() >=2){
            // 为出现频率最少的两个字符创建一个父节点
            HuffmanNode x = huffmanQueue.poll();
            HuffmanNode y = huffmanQueue.poll();
            HuffmanNode huffmanNode = new HuffmanNode(x.freq + y.freq, x, y);
            // 在将父节点放入优先级队列当中
            huffmanQueue.offer(huffmanNode);
        }
        // 队列中的最后一个节点即为根节点
         root = huffmanQueue.poll();
        // 计算每个字符的编码(使用深度优先算法)
        int dfs = dfs(root, new StringBuilder());
        System.out.println("总共占用的bits位："+dfs);
    }

    private int dfs(HuffmanNode root, StringBuilder stringBuilder) {
        // 计算编码所需的bite位
        int sum = 0;
        if (root.isLeaf()){
            // 在哈夫曼树中找到了当前字符所在的位置
            root.code = stringBuilder.toString();
            // 用字符在哈夫曼树中的长度 * 使用频率计算
            sum = stringBuilder.length() * root.freq;
        }else {
            // 在哈夫曼树中向左子树编码就为0；
            stringBuilder.append("0");
            sum += dfs(root.left,stringBuilder);
            // 当父节点的左子树遍历完成以后该遍历右子树，所以需要将左子树的最后一个编码删除
             stringBuilder.deleteCharAt(stringBuilder.length()-1);
            stringBuilder.append("1");
            sum += dfs(root.right,stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        return sum;
    }

    public String enCode(){
        char[] chars = str.toCharArray();
        StringBuilder builder = new StringBuilder();
        for (char aChar : chars) {
            HuffmanNode huffmanNode = hashMap.get(aChar);
            builder.append( huffmanNode.code);
        }
        return builder.toString();
    }
    public String deCode(String str){
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        int index = 0;
        HuffmanNode node =root;
        while (index < chars.length){
            // 判断当前是否是叶子节点，是叶子节点时无对应的char
            if (!node.isLeaf()){
                if (chars[index] =='0' ){
                    node = node.left;
                }else if (chars[index] == '1'){
                    node = node.right;
                }
                index++;
            }
            if (node.isLeaf()){
                sb.append(node.ch);
                node = root;
            }


        }
        return sb.toString();
    }

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree("abbccccccc");
        String s = huffmanTree.enCode();
        System.out.println(s);
        System.out.println(huffmanTree.deCode(s));
    }

}
